//
// Created by xili on 2024/8/24 16:47.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int n;

    int shipWithinDays(vector<int> &weights, int days) {
        n = weights.size();
        vector<int> help(weights.begin(), weights.end());
        sort(help.begin(), help.end());
        int k = ceil((float) n / days);
        int r = 0;
        for (int i = n - k; i < n; i++) {
            r += help[i];
        }
        int l = help[n - 1];
        int ans = l;
        while (l <= r) {
            int m = (l + r) >> 1;
            if (ok(weights, days, m)) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }

    bool ok(vector<int> &weights, int days, int w) {
        int d = 1;
        int cur = w;
        for (int i = 0; i < n; i++) {
            if (cur - weights[i] >= 0) {
                cur -= weights[i];
            } else {
                d++;
                cur = w - weights[i];
            }
        }
        return d <= days;
    }
};